package com.leetcode.algorithm.y21.m07;

/**
 * leetcode-cn.com
 * 
 * (done)509. 斐波那契数
 * (done)1137. 第 N 个泰波那契数
 * 
 * @author jie.deng
 *
 */
public class MySolution0708 {
	
    
    /**
     * 509. 斐波那契数
     * 
     * 斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
     * 
     * F(0) = 0,   F(1) = 1
     * F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
     * 给定 N，计算 F(N)。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：2
     * 输出：1
     * 解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
     * 示例 2：
     * 
     * 输入：3
     * 输出：2
     * 解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
     * 示例 3：
     * 
     * 输入：4
     * 输出：3
     * 解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
     *  
     * 
     * 提示：
     * 
     * 0 ≤ N ≤ 30
     * @param n
     * @return
     */
    public int fib(int n) {
		if (n == 0 || n == 1) {
			return n;
		}
		int n0 = 0, n1 = 1, i = 2;
		while (i < n) {
			int tmp = n0 + n1;
			n0 = n1;
			n1 = tmp;
			i++;
		}
		return n0 + n1;
    }

    
    /**
     * 
     * 1137. 第 N 个泰波那契数
     * 
     * 泰波那契序列 Tn 定义如下： 
     * 
     * T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
     * 
     * 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：n = 4
     * 输出：4
     * 解释：
     * T_3 = 0 + 1 + 1 = 2
     * T_4 = 1 + 1 + 2 = 4
     * 示例 2：
     * 
     * 输入：n = 25
     * 输出：1389537
     *  
     * 
     * 提示：
     * 
     * 0 <= n <= 37
     * 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/n-th-tribonacci-number
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param n
     * @return
     */
	public int tribonacci(int n) {
		if (n == 0) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return 1;
		}
		int i0 = 0, i1 = 1, i2 = 1, idx = 3;
		while (idx < n) {
			int tmp = i0 + i1 + i2;
			i0 = i1;
			i1 = i2;
			i2 = tmp;
			idx++;
		}
		return i0 + i1 + i2;
	}
    
}
